﻿#define _CRT_SECURE_NO_WARNINGS 1

class Solution
{
public:
	vector<int> sortArray(vector<int>& nums)
	{
		srand(time(NULL)); // 种下⼀个随机数种⼦
		qsort(nums, 0, nums.size() - 1);
		return nums;
	}
	// 快排
	void qsort(vector<int>& nums, int l, int r)
	{
		if (l >= r) return;
		// 数组分三块
		int key = getRandom(nums, l, r);
		int i = l, left = l - 1, right = r + 1;
		while (i < right)
		{
			if (nums[i] < key) swap(nums[++left], nums[i++]);
			else if (nums[i] == key) i++;
			else swap(nums[--right], nums[i]);
		}
		// [l, left] [left + 1, right - 1] [right, r]
		qsort(nums, l, left);
		qsort(nums, right, r);
	}
	int getRandom(vector<int>& nums, int left, int right)
	{
		int r = rand();
		return nums[r % (right - left + 1) + left];
	}
};